package com.etc.homework;

import java.util.Arrays;
import java.util.Random;

/**
 * @author: knowno
 * @create: 2024-09-04 10:29
 * @Version 1.0
 * <p>
 * 插入排序与选择排序类似，需要将数组分为有序与无序两部分。但插入不会去到无序部分选择，而是随意选取一个无序部分元素到有序部分中寻找它所在的位置进行插入保持有序部分仍然有序。
 * <p>
 * 插入排序排序运算主要集中在查找位置及元素的移动上,如果在链表中进行插入排序,会比数组中排序效率高
 **/
public class InsertionSort {

    /**
     * @param arr
     */

    public static void insertionSorting(Student[] arr) {
        //将当前元素保存起来，后续要存储到"指定"位置
        Student curr;
        for (int i = 1; i < arr.length; i++) {
            //给curr赋值
            curr = arr[i];
            //内循环，比较，找到合适的位置,从右侧向左侧比较
            for (int j = i - 1; j >= 0; j--) {
                //判断
                if (curr.getHeight() < arr[j].getHeight()) {
                    arr[j + 1] = arr[j];
                } else {
                    //找到了curr应该存储的位置
                    arr[j + 1] = curr;
                    break;

                }
                //如果j的值为0,数组的起始位置, 此时同样将curr的值存储
                if (j == 0) {
                    arr[j] = curr;
                }
            }
        }


    }

}

